package 力扣日常刷题.木22二月.第18天224;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author 帅小伙
 * @date 2022/2/25
 * @description
 */
public class Demo148字节跳动2017后端工程师实习生笔试题4 {


    static ArrayList<String> lists  = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(),K = scanner.nextInt();
        int ans = 0;
        String[] strings = new String[n];
        StringBuffer sb = new StringBuffer();

        for (int i = 0; i < n; i++) {
            strings[i] = scanner.next();
            sb.append(strings[i]);
        }
        K%=sb.length();
        String target = sb.toString();
        dfs(strings,new boolean[strings.length],new StringBuffer(),0);

        for (String list : lists) {
            list += list;
            int t = 0;
            for (int i = 0; i < list.length() /2; i++) {
                String substring = list.substring(i, list.length() / 2 + i);
                if(substring.equals(target)) t++;
            }
            if(t == K) ans ++;
        }
        System.out.println(ans);
    }


    public static void dfs(String[] strings,boolean[] isUsed,StringBuffer sb,int index){
        if(index == strings.length) {
            lists.add(sb.toString());
            return ;
        }

        for (int i = 0; i < strings.length; i++) {
            if(!isUsed[i]) {
                int len = strings[i].length();
                sb.append(strings[i]);
                isUsed[i] = true;
                dfs(strings,isUsed,sb,index+1);
                sb.delete(sb.length() - len,sb.length());
                isUsed[i] = false;
            }
        }
    }
}
